#include<bits/stdc++.h>

using namespace std;
using ll = long long;
#define endl '\n'

//T(n)=O(1)+T(n/2)=>T(n)=O(lgN)
bool Binary_search(int *a, int left, int right, int key) {
    if (left > right)return false;
    if (left == right)return a[left] == key;
    int mid = (left + right) / 2;
    if (key == a[mid]) {
        return true;
    }
    if (key < a[mid]) {
        return Binary_search(a, left, mid - 1);
    }
    return Binary_search(a, mid + 1, right);

}

int main() {
    int a[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    sort(a, a + 10);
    int k = 3;
    bool flag = Binary_search(a, 0, 9, k);
    cout << flag;
    return 0;
}
